//#include <pmm.h>
//#include <list.h>
//#include <string.h>
//#include <best_fit_pmm.h>
//#include <stdio.h>
//
///* In the first fit algorithm, the allocator keeps a list of free blocks (known as the free list) and,
//   on receiving a request for memory, scans along the list for the first block that is large enough to
//   satisfy the request. If the chosen block is significantly larger than that requested, then it is 
//   usually split, and the remainder added to the list as another free block.
//   Please see Page 196~198, Section 8.2 of Yan Wei Min's chinese book "Data Structure -- C programming language"
//*/
//
//// you should rewrite functions: default_init,default_init_memmap,default_alloc_pages, default_free_pages.
///*
// * Details of FFMA
// * (1) Prepare: In order to implement the First-Fit Mem Alloc (FFMA), we should manage the free mem block use some list.
// *              The struct free_area_t is used for the management of free mem blocks. At first you should
// *              be familiar to the struct list in list.h. struct list is a simple doubly linked list implementation.
// *              You should know howto USE: list_init, list_add(list_add_after), list_add_before, list_del, list_next, list_prev
// *              Another tricky method is to transform a general list struct to a special struct (such as struct page):
// *              you can find some MACRO: le2page (in memlayout.h), (in future labs: le2vma (in vmm.h), le2proc (in proc.h),etc.)
// * (2) default_init: you can reuse the  demo default_init fun to init the free_list and set nr_free to 0.
// *              free_list is used to record the free mem blocks. nr_free is the total number for free mem blocks.
// * (3) default_init_memmap:  CALL GRAPH: kern_init --> pmm_init-->page_init-->init_memmap--> pmm_manager->init_memmap
// *              This fun is used to init a free block (with parameter: addr_base, page_number).
// *              First you should init each page (in memlayout.h) in this free block, include:
// *                  p->flags should be set bit PG_property (means this page is valid. In pmm_init fun (in pmm.c),
// *                  the bit PG_reserved is setted in p->flags)
// *                  if this page  is free and is not the first page of free block, p->property should be set to 0.
// *                  if this page  is free and is the first page of free block, p->property should be set to total num of block.
// *                  p->ref should be 0, because now p is free and no reference.
// *                  We can use p->page_link to link this page to free_list, (such as: list_add_before(&free_list, &(p->page_link)); )
// *              Finally, we should sum the number of free mem block: nr_free+=n
// * (4) default_alloc_pages: search find a first free block (block size >=n) in free list and reszie the free block, return the addr
// *              of malloced block.
// *              (4.1) So you should search freelist like this:
// *                       list_entry_t le = &free_list;
// *                       while((le=list_next(le)) != &free_list) {
// *                       ....
// *                 (4.1.1) In while loop, get the struct page and check the p->property (record the num of free block) >=n?
// *                       struct Page *p = le2page(le, page_link);
// *                       if(p->property >= n){ ...
// *                 (4.1.2) If we find this p, then it' means we find a free block(block size >=n), and the first n pages can be malloced.
// *                     Some flag bits of this page should be setted: PG_reserved =1, PG_property =0
// *                     unlink the pages from free_list
// *                     (4.1.2.1) If (p->property >n), we should re-caluclate number of the the rest of this free block,
// *                           (such as: le2page(le,page_link))->property = p->property - n;)
// *                 (4.1.3)  re-caluclate nr_free (number of the the rest of all free block)
// *                 (4.1.4)  return p
// *               (4.2) If we can not find a free block (block size >=n), then return NULL
// * (5) default_free_pages: relink the pages into  free list, maybe merge small free blocks into big free blocks.
// *               (5.1) according the base addr of withdrawed blocks, search free list, find the correct position
// *                     (from low to high addr), and insert the pages. (may use list_next, le2page, list_add_before)
// *               (5.2) reset the fields of pages, such as p->ref, p->flags (PageProperty)
// *               (5.3) try to merge low addr or high addr blocks. Notice: should change some pages's p->property correctly.
// */
//free_area_t free_area;
//
//#define free_list (free_area.free_list)
//#define nr_free (free_area.nr_free)
//
//static void
//best_fit_init(void) {
//    list_init(&free_list);
//    nr_free = 0;
//}
//
//static void
//best_fit_init_memmap(struct Page *base, size_t n) {
//    assert(n > 0);
//    struct Page *p = base;
//    for (; p != base + n; p ++) {
//        assert(PageReserved(p));
//
//        /*LAB2 EXERCISE 2: YOUR CODE*/ 
//        // 清空当前页框的标志和属性信息，并将页框的引用计数设置为0
//        p->flags = 0;
//        p->property = 0;    //property：空闲的block数量。
//        set_page_ref(p, 0);
//    }
//    base->property = n;
//    SetPageProperty(base);
//    nr_free += n;
//    if (list_empty(&free_list)) {
//        list_add(&free_list, &(base->page_link));
//    } else {
//        list_entry_t* le = &free_list;
//        while ((le = list_next(le)) != &free_list) {    //它从链表头开始遍历可用页面链表。
//            struct Page* page = le2page(le, page_link);
//             /*LAB2 EXERCISE 2: YOUR CODE*/ 
//            // 编写代码
//            // 1、当base < page时，找到第一个大于base的页，将base插入到它前面，并退出循环
//            if (base < page)
//            {
//                list_add_before(le, &(base->page_link));
//                break;
//            }
//            // 2、当list_next(le) == &free_list时，若已经到达链表结尾，将base插入到链表尾部
//            else if (list_next(le) == &free_list)
//            {
//                list_add(le, &(base->page_link));
//            }
//        }
//    }
//}
//
//static struct Page *
//best_fit_alloc_pages(size_t n) {
//    assert(n > 0);
//    if (n > nr_free) {
//        return NULL;
//    }
//    struct Page *page = NULL;
//    list_entry_t *le = &free_list;
//    size_t min_size = nr_free + 1;
//     /*LAB2 EXERCISE 2: YOUR CODE*/ 
//    // 下面的代码是first-fit的部分代码，请修改下面的代码改为best-fit
//    // 遍历空闲链表，查找满足需求的空闲页框
//    // 如果找到满足需求的页面，记录该页面以及当前找到的最小连续空闲页框数量
//    unsigned int min_property = 1145141919;
//    while ((le = list_next(le)) != &free_list) {
//        struct Page *p = le2page(le, page_link);
//        if (p->property >= n && p->property < min_property) {
//            page = p;
//            min_property = p->property;
//        }
//    }
//
//
//
//    if (page != NULL) {
//        list_entry_t* prev = list_prev(&(page->page_link));
//        list_del(&(page->page_link));
//        if (page->property > n) {
//            struct Page *p = page + n;
//            p->property = page->property - n;
//            SetPageProperty(p);
//            list_add(prev, &(p->page_link));
//        }
//        nr_free -= n;
//        ClearPageProperty(page);
//    }
//    return page;
//}
//
//static void
//best_fit_free_pages(struct Page *base, size_t n) {
//    //虽然但是这部分best-fit和first-fit应该是一样的。
//    assert(n > 0);
//    struct Page *p = base;
//    for (; p != base + n; p ++) {
//        assert(!PageReserved(p) && !PageProperty(p)); //意味着只要这n个页面中有一个是保留页面或者属性页面，那么这个函数直接停止。
//        p->flags = 0;                                 //声明这个页面不在使用
//        set_page_ref(p, 0);                           //不再存在对该页面的引用。
//    }
//    /*LAB2 EXERCISE 2: YOUR CODE*/ 
//    // 编写代码
//    // 具体来说就是设置当前页块的属性为释放的页块数、并将当前页块标记为已分配状态、最后增加nr_free的值
//    base->property = n;
//    SetPageProperty(base);
//    nr_free += n;
//
//    //这部分维护链表。如果是空的，直接添加，否则按顺序插入。
//    if (list_empty(&free_list)) {
//        list_add(&free_list, &(base->page_link));
//    } else {
//        list_entry_t* le = &free_list;
//        while ((le = list_next(le)) != &free_list) {
//            struct Page* page = le2page(le, page_link);
//            if (base < page) {
//                list_add_before(le, &(base->page_link));
//                break;
//            } else if (list_next(le) == &free_list) {
//                list_add(le, &(base->page_link));
//            }
//        }
//    }
//
//    //在这部分是进一步合并、善后。
//    //这里是分别向前看、向后看了，先向前看，看看是不是连着的。
//    list_entry_t* le = list_prev(&(base->page_link));
//    if (le != &free_list) {//如果如果前一个不是空的
//        p = le2page(le, page_link);
//        /*LAB2 EXERCISE 2: YOUR CODE*/ 
//         // 编写代码
//        // 1、判断前面的空闲页块是否与当前页块是连续的，如果是连续的，则将当前页块合并到前面的空闲页块中
//        // 2、首先更新前一个空闲页块的大小，加上当前页块的大小
//        // 3、清除当前页块的属性标记，表示不再是空闲页块
//        // 4、从链表中删除当前页块
//        // 5、将指针指向前一个空闲页块，以便继续检查合并后的连续空闲页块
//        if (p + p->property == base)//base的前一个加上它有的空闲块数量正好等于base，意味着他们俩连着。
//        {
//            p->property += base->property;      //p：property？拿来吧你！
//                                                //base：我什么都做不了，呜呜呜好可怜啊
//            ClearPageProperty(base);            //杀人诛心
//            list_del(&(base->page_link));       //抹除存在
//            base = p;                           //base：没想到吧，我能反杀！如果是后面连续的话，就不用这一步了，因为base本来就在前面
//        }
//    }
//
//    le = list_next(&(base->page_link));
//    if (le != &free_list) {
//        p = le2page(le, page_link);
//        if (base + base->property == p) {
//            base->property += p->property;
//            ClearPageProperty(p);
//            list_del(&(p->page_link));
//        }
//    }
//}
//
//static size_t
//best_fit_nr_free_pages(void) {
//    return nr_free;
//}
//
//static void
//basic_check(void) {
//    struct Page *p0, *p1, *p2;
//    p0 = p1 = p2 = NULL;
//    assert((p0 = alloc_page()) != NULL);
//    assert((p1 = alloc_page()) != NULL);
//    assert((p2 = alloc_page()) != NULL);
//
//    assert(p0 != p1 && p0 != p2 && p1 != p2);
//    assert(page_ref(p0) == 0 && page_ref(p1) == 0 && page_ref(p2) == 0);
//
//    assert(page2pa(p0) < npage * PGSIZE);
//    assert(page2pa(p1) < npage * PGSIZE);
//    assert(page2pa(p2) < npage * PGSIZE);
//
//    list_entry_t free_list_store = free_list;
//    list_init(&free_list);
//    assert(list_empty(&free_list));
//
//    unsigned int nr_free_store = nr_free;
//    nr_free = 0;
//
//    assert(alloc_page() == NULL);
//
//    free_page(p0);
//    free_page(p1);
//    free_page(p2);
//    assert(nr_free == 3);
//
//    assert((p0 = alloc_page()) != NULL);
//    assert((p1 = alloc_page()) != NULL);
//    assert((p2 = alloc_page()) != NULL);
//
//    assert(alloc_page() == NULL);
//
//    free_page(p0);
//    assert(!list_empty(&free_list));
//
//    struct Page *p;
//    assert((p = alloc_page()) == p0);
//    assert(alloc_page() == NULL);
//
//    assert(nr_free == 0);
//    free_list = free_list_store;
//    nr_free = nr_free_store;
//
//    free_page(p);
//    free_page(p1);
//    free_page(p2);
//}
//
//// LAB2: below code is used to check the best fit allocation algorithm 
//// NOTICE: You SHOULD NOT CHANGE basic_check, default_check functions!
//static void
//best_fit_check(void) {
//    int score = 0 ,sumscore = 6;
//    int count = 0, total = 0;
//    list_entry_t *le = &free_list;
//    while ((le = list_next(le)) != &free_list) {
//        struct Page *p = le2page(le, page_link);
//        assert(PageProperty(p));
//        count ++, total += p->property;
//    }
//    assert(total == nr_free_pages());
//
//    basic_check();
//
//    #ifdef ucore_test
//    score += 1;
//    cprintf("grading: %d / %d points\n",score, sumscore);
//    #endif
//    struct Page *p0 = alloc_pages(5), *p1, *p2;
//    assert(p0 != NULL);
//    assert(!PageProperty(p0));
//
//    #ifdef ucore_test
//    score += 1;
//    cprintf("grading: %d / %d points\n",score, sumscore);
//    #endif
//    list_entry_t free_list_store = free_list;
//    list_init(&free_list);
//    assert(list_empty(&free_list));
//    assert(alloc_page() == NULL);
//
//    #ifdef ucore_test
//    score += 1;
//    cprintf("grading: %d / %d points\n",score, sumscore);
//    #endif
//    unsigned int nr_free_store = nr_free;
//    nr_free = 0;
//
//    // * - - * -
//    free_pages(p0 + 1, 2);
//    free_pages(p0 + 4, 1);
//    assert(alloc_pages(4) == NULL);
//    assert(PageProperty(p0 + 1) && p0[1].property == 2);
//    // * - - * *
//    assert((p1 = alloc_pages(1)) != NULL);
//    assert(alloc_pages(2) != NULL);      // best fit feature
//    assert(p0 + 4 == p1);
//
//    #ifdef ucore_test
//    score += 1;
//    cprintf("grading: %d / %d points\n",score, sumscore);
//    #endif
//    p2 = p0 + 1;
//    free_pages(p0, 5);
//    assert((p0 = alloc_pages(5)) != NULL);
//    assert(alloc_page() == NULL);
//
//    #ifdef ucore_test
//    score += 1;
//    cprintf("grading: %d / %d points\n",score, sumscore);
//    #endif
//    assert(nr_free == 0);
//    nr_free = nr_free_store;
//
//    free_list = free_list_store;
//    free_pages(p0, 5);
//
//    le = &free_list;
//    while ((le = list_next(le)) != &free_list) {
//        struct Page *p = le2page(le, page_link);
//        count --, total -= p->property;
//    }
//    assert(count == 0);
//    assert(total == 0);
//    #ifdef ucore_test
//    score += 1;
//    cprintf("grading: %d / %d points\n",score, sumscore);
//    #endif
//}
////这个结构体在
//const struct pmm_manager best_fit_pmm_manager = {
//    .name = "best_fit_pmm_manager",
//    .init = best_fit_init,
//    .init_memmap = best_fit_init_memmap,
//    .alloc_pages = best_fit_alloc_pages,
//    .free_pages = best_fit_free_pages,
//    .nr_free_pages = best_fit_nr_free_pages,
//    .check = best_fit_check,
//};
//
